package com.zofer.study.search;

/**
 * @description 二分查找 输出在数组中第一个大于等于查找值的位置
 * @date: 2020/10/9 17:25
 * @author zofer
 */
public class FirstEqualOrMoreByBinarySearch {


    /**
     * 题目：请实现有重复数字的有序数组的二分查找。
     * 输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
     *
     */
    public int upper_bound_ (int n, int v, int[] a) {
        int start = 0;
        int end = a.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (a[mid] >= v) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return start+1;
    }
}
